The present invention is directed to networks used for forwarding information packets and, more particularly, to networks which incorporate multi-protocol label switching (MPLS).
Networks that use multi-protocol label switching (MPLS) permit the transfer of packets through the network via an end-to-end connection path that is determined before the packets are transferred through the network. When a packet enters the MPLS network, the packet is assigned a “label” by an ingress router, also known as a label edge router (LER), which also attaches the label to the packet and forwards the packet to the first one of a series of routers, known as label switch routers (LSRs), that forward the packet along the connection path. The label includes information that is used by the first router to determine the next router to which the packet is to be forwarded. The first router then receives the packet, removes the label, and then attaches a new label that is to be used by the next router to determine the subsequent router to which the packet is to be switched. This process is repeated for each router located along the connection path. Namely, each router along the path receives the packet with a label attached by the immediately preceding router, uses the information contained in the label to determine the next router to receive the packet, strips the current label, applies a new label that is to be used by the succeeding router, and then forwards the packet to that router. The process ends when the packet is delivered to the last router along the path, also known as an egress router or an LER.
Because labels are used to determine how each router forwards packets along the connection path, also known as forwarding traffic, the connection path is also known as a label-switched path (LSP). Each label contains information about only a portion of the LSP, and each router or switch need only store information regarding the route corresponding to a particular label and store the next label to be attached to the packet.
The specific routes that comprise the LSP are typically determined based on a variety of reasons, such as to guarantee a certain level of performance, to route around network congestion, or to comply with the requirements of the specific application. One or more backup LSPs are also typically determined at the same time when a primary LSP is set up. The routes for the backup paths may be determined either statically during the primary LSP set up or may be determined dynamically only upon a primary LSP failure. The backup paths typically have the same bandwidth as the primary LSP.
When a failure occurs in the network, such as when a router failure, a router interface failure or a link failure occurs, the packets that were carried over the failed LSP are switched over to one of its corresponding backup LSPs. Sometimes, however, the network failure may also cause a failure of the primary LSP and its backup LSP. The present MPLS network recovery schemes do not address such situations.
It is therefore desirable to have a traffic restoration scheme that handles such situations in order to increase network availability and service availability. It is also desirable to have such a scheme create one or more replacement LSPs that carries as much of the traffic as possible that was carried by the failed LSP. It is further desirable that the restoration scheme creates replacement LSPs by considering efficient utilization of network resources and using traffic engineering policies.